package btree;

public class BTree {

    static class BTreeNode{
        public int[] keys;//关键字
        public BTreeNode[] subs;//孩子
        public BTreeNode parent;//当前孩子节点的父节点
        public int usedSize;//当前节点中关键字的数量

        public BTreeNode() {
            this.keys=new int[M];
            this.subs=new BTreeNode[M+1];
        }
    }
    public static final int M=3;
    public BTreeNode root;//当前B树的根节点
    //插入元素
    public boolean insert(int key){
        //1、如果B树为空
        if(root==null){
            root=new BTreeNode();
            root.keys[0]=key;
            root.usedSize++;
            return true;
        }
        //2、如果B树不为空，需要查找B树中是否存在key
        Pair<BTreeNode, Integer>  pair = find(key);
        if(pair.getVal()!=-1){
            return false;
        }
        BTreeNode parent = pair.getKey();
        int index= parent.usedSize-1;
        for (; index >= 0 ; index--) {
            if(parent.keys[index]>=key){
                parent.keys[index+1]=parent.keys[index];
            }else{
                break;
            }
        }
        parent.keys[index+1]=key;
        parent.usedSize++;
        if(parent.usedSize < M){
            return true;
        }else{
            split(parent);//分裂
            return true;
        }
    }

    //分裂
    private void split(BTreeNode cur) {
        BTreeNode newNode=new BTreeNode();
        //先存储当前需要分裂节点的父节点
        BTreeNode parent=cur.parent;
        //开始挪数据
        int mid=cur.usedSize/2;
        int i = mid+1;
        int j=0;
        for (; i < cur.usedSize; i++) {
            newNode.keys[j]=cur.keys[i];
            newNode.subs[j]=cur.subs[i];
            if(newNode.subs[j]!=null){
                newNode.subs[j].parent=newNode;
            }
            j++;
        }
        //多拷贝一次孩子
        newNode.subs[j]=cur.subs[i];
        if(newNode.subs[j]!=null){
            newNode.subs[j].parent=newNode;
        }
        newNode.usedSize=j;
        //这里的-1是指 将来要提到父亲节点的key
        cur.usedSize= cur.usedSize-j-1;
        //处理根节点的情况
        if(cur==root){
            root=new BTreeNode();
            root.keys[0]=cur.keys[mid];
            root.subs[0]=cur;
            root.subs[1]=newNode;
            root.usedSize=1;
            cur.parent=root;
            newNode.parent=root;
            return;
        }
        //更新当前新的节点的父亲节点
        newNode.parent=parent;
        //开始移动父亲节点
        int endT=parent.usedSize-1;
        int midVal=cur.keys[mid];
        for (; endT >=0 ; endT--) {
            if(parent.keys[endT]>=midVal){
                parent.keys[endT+1]=parent.keys[endT];
                parent.subs[endT+2]=parent.subs[endT+1];
            }else{
                break;
            }
        }
        parent.keys[endT+1]=midVal;
        //将当前父亲节点的孩子节点 新增为newNode
        parent.subs[endT+2]=newNode;
        parent.usedSize++;
        if(parent.usedSize>=M){
            split(parent);
        }
    }

    private Pair<BTreeNode,Integer> find(int key){
        BTreeNode cur=root;
        BTreeNode parent=null;
        while(cur!=null){
            int i=0;
            while(i<cur.usedSize){
                if(cur.keys[i]==key){
                    return new Pair<>(cur,i);
                }else if(cur.keys[i]<key){
                    i++;
                }else{
                    break;
                }
            }
            parent=cur;
            cur=cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }
    public void inorder(BTreeNode root){
        if(root == null){
            return;
        }
        for(int i = 0; i < root.usedSize; ++i){
            inorder(root.subs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.subs[root.usedSize]);

    }
}
